#include <vector>

using namespace std;

class MountainArray {
private:
    vector<int> data;
public:
    MountainArray(vector<int> data) {
        this->data = data;
    }
    int get(int index) {
        return data[index];
    }
    int length() {
        return data.size();
    }
};

class Solution {
private:
    int binary_search1(int left, int right, MountainArray &mountainArr, int& target) {
        if (left >= right) {
            return mountainArr.get(left) == target ? left : -1;
        }
        int middle = (left + right) / 2;
        if (mountainArr.get(middle) == target) {
            return middle;
        } else if (mountainArr.get(middle) < target) {
            return binary_search1(middle + 1, right, mountainArr, target);
        } else {
            return binary_search1(left, middle - 1, mountainArr, target);
        }
    }
    int binary_search2(int left, int right, MountainArray &mountainArr, int& target) {
        if (left >= right) {
            return mountainArr.get(left) == target ? left : -1;
        }
        int middle = (left + right) / 2;
        if (mountainArr.get(middle) == target) {
            return middle;
        } else if (mountainArr.get(middle) < target) {
            return binary_search2(left, middle - 1, mountainArr, target);
        } else {
            return binary_search2(middle + 1 , right, mountainArr, target);
        }
    }
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int left = 0;
        int right = mountainArr.length() - 1;
        while (left < right) {
            int middle = (left + right) / 2;
            if (mountainArr.get(middle) < mountainArr.get(middle + 1)) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }
        int ans = binary_search1(0, left, mountainArr, target);
        if (ans != -1) {
            return ans;
        }
        return binary_search2(left, mountainArr.length() - 1, mountainArr, target);
    }
};